import java.util.*;

/**
 * Clase de objetos que representan una configuracion valida de un numero menor o igual que n reinas correctamente colocadas
 * en un tablero nxn. En caso de que se hayan colocado n reinas, el objeto representa un solucion al problema de las n reinas.
 * Dado que no existe solucion a los problemas para n=2 y n=3 (para n=1 es trivial), se supone siempre que n>3.
 *  
 * @author    Jose Antonio Perez Castellanos
 * @version      1.0 Curso 10/11
 */
public class TableroReinas implements Cloneable
{
    private int tamanyo;            // Tamanyo del tablero
    private int tablero[];        // Configuracion del tablero: tablero[c]= f (f>=0) <-> hay una reina en la fila f de la columna c. 
                                  //                               tablero[c]= -1       <-> la columna c (y posteriores) no tiene ninguna reina
    private boolean fila_segura[];             // fila_segura[i] == true            <-> la fila i no tiene aun ninguna reina
    private boolean diagonal_neg_segura[];   // diagonal_neg_segura[i] == true <-> la diagonal de arriba-derecha a abajo-izquierda i no contiene ninguna reina
    private boolean diagonal_pos_segura[];   // diagonal_pos_segura[i] == true <-> la diagonal de arriba-izquierda a abajo-derecha i no contiene ninguna reina

    /**
    *  Constructor no-arg para uso exclusivo de metodo clone()
    */    
    private TableroReinas()
    {
        super();
    }
    /**
     *  Constructor que crea un tablero vacio de tamanyo n
     * 
     * @param tamanyo Tamanyo del tablero que se crea. 
     */    
    public TableroReinas(int tamanyo)
    {
        super();
        this.tamanyo = tamanyo;
        tablero = new int[tamanyo];
        for (int i = 0; i < tamanyo; i++)
            tablero[i] = -1;
        fila_segura = new boolean[tamanyo];
        for(int i = 0; i< fila_segura.length; i++)
          fila_segura[i] = true;
        diagonal_neg_segura = new boolean[tamanyo * 2 - 1];
        for(int i = 0; i < diagonal_neg_segura.length; i++)
          diagonal_neg_segura[i] = true;
        diagonal_pos_segura = new boolean[tamanyo * 2 - 1];
        for(int i = 0; i < diagonal_pos_segura.length; i++)
          diagonal_pos_segura[i] = true;
    }

    // Constructor para crear a partir de un estado actual
    public TableroReinas(int[] estadoActual, boolean calcularInfoAdicional)
    {
        // FIXME se puede optimizar porque cuando un colaborador
        // devuelve el array no hace falta "colocar la reina" y
        // anyadir la informacion de las diagonales, solo nos interesa
        // el resultado final y el tamanyo como en cloneSolucion()
        this(estadoActual.length);
        
        if (calcularInfoAdicional)
        {
            for(int i = 0 ; i < estadoActual.length ; i++)
            {
                if(estadoActual[i] == -1)
                    break;

                colocarReina(estadoActual[i], i);
            }
        }
    }

    /**
     *  Coloca una reina en la posicion fila,columna del tablero. Importante: se supone que (i) no hay ninguna reina colocada
     *  en columnas por encima de la especificada, y (ii) que todas las reinas colocadas en columnas anteriores a la especificada 
     *  estan en posiciones seguras.
     * 
     * @param fila Fila en la que se coloca la reina
     * @param columna Columna en la que se coloca la reina 
     */        
    public void colocarReina (int fila, int columna)
    {
        tablero[columna] = fila;                               // Colocamos la reina
        fila_segura[fila] = false;                              // Marcamos como ocupadas la fila y ambas diagonales
        diagonal_neg_segura[fila + columna] = false;              
        diagonal_pos_segura[fila - columna + tamanyo - 1] = false;
    }
    
    /**
     *  Quita una reina previamente colocada en la fila dada del tablero.
     *  Importante: se supone que (i) hay una
     *  reina colocada en la columna dada,
     *  (ii) que no hay reinas colocadas mas alla de esta columna, y (iii) que 
     *  todas las reinas colocadas en columnas anteriores a
     *  la actual estan colocadas en posiciones seguras.
     * 
     * @param fila columna de la cual se quita la reina
     */        
    public void quitarReina (int columna)
    {
        int fila = tablero[columna];
        tablero[columna] = -1;                                // Quitamos la reina
        fila_segura[fila] = true;                              // Marcamos como libres la fila y ambas diagonales
        diagonal_neg_segura[fila + columna] = true;              
        diagonal_pos_segura[fila-columna+tamanyo-1] = true;
    }

    /**
     *  Comprueba si se puede colocar una reina en la posicion fila,columna del tablero. Importante: se supone
     *  que no hay ya una reina colocada en la misma columna (no tendria sentido pues evidentemente no seria
     *  segura la columna). Solo se comprueba que no haya ninguna reina en la misma fila ni en la misma diagonal. 
     * 
     * @param fila Fila de la posicion que se comprueba
     * @param fila Columna de la posicion que se comprueba
     * @return true si la posicion fila,columna es segura, false en caso contrario.
     */        
    public boolean posicionSegura (int fila, int columna)
    {
        /*
        boolean a = fila_segura[fila];
        boolean b =diagonal_neg_segura[fila + columna];
        boolean c =diagonal_pos_segura[fila - columna + tamanyo - 1];
        */
        return (fila_segura[fila] && diagonal_neg_segura[fila + columna] && diagonal_pos_segura[fila - columna + tamanyo - 1]);
    }
    
    /** 
     *  Clonacion de un tablero. Crea un tablero identico al actual.
     *  
     *  @return Tablero identico al actual.
     */        

    public TableroReinas clone()
    {
        TableroReinas resultado = new TableroReinas();
        
        resultado.tamanyo = tamanyo;
        resultado.tablero = tablero.clone();
        resultado.fila_segura = fila_segura.clone();
        resultado.diagonal_pos_segura = diagonal_pos_segura.clone();
        resultado.diagonal_neg_segura = diagonal_neg_segura.clone();
        
        return resultado;
    }

    public int getTamanyo()
    {
        return tamanyo;
    }

    public int getColumnasCompletadas()
    {
        int i = 0;
        while(i < tamanyo && tablero[i] != -1)
            i++;

        return i;
    }
    
    /**
     *  Clonacion de una solucion. En el caso de que la configuracion expresada sea una solucion,
     *  no es necesario clonar los vectores empleados para anotar las filas y diagonales libres u ocupadas,
     *  lo cual llega a ser un alivio cuando el numero de soluciones crece combinatoriamente.
     *  
     *  @return Tablero con identica configuracion al actual y sin informacion sobre filas y diagonales libres.
     */        
    public TableroReinas cloneSolucion()
    {
        TableroReinas resultado = new TableroReinas();
        
        resultado.tamanyo = tamanyo;
        resultado.tablero = tablero.clone();
        
        return resultado;
    }

    /**
     *  Conversion a cadena de un tablero, para facilitar la interpretacion de los resultados. 
     *  
     *  @return Representacion textual del tablero.
     */        
    public String toString()
    {
        String resultado = "" + tablero[0];
        
        for (int i = 1; i < tamanyo; i++)
          resultado = resultado + ", " + tablero[i];
        
        return resultado;
    }

    public int[] toArray()
    {
        return tablero.clone();
    }
}
